#Wstęp

W niniejszym raporcie będziemy porównywać metodę k–średnich oraz k–medoidów.

1 Dane

Posłużymy się do tego celu syntetycznymi danymi do benchmarków – zbiorze a1.

Posiada on \(3000\) obserwacji oraz \(20\) klastrów. Rozkład przeskalowanych danych wraz z oryginalnymi etykietami prezentujemy na poniższym wykresie:

ggplot(data = dataset, aes(x = x, y = y, color = as.factor(label))) + 
  geom_point()

2 Klasteryzacja

Teraz dokonamy klasteryzacji korzystając z funkcji kmeans (metoda k–średnich) z wbudowanego pakietu stats oraz z funkcji pam (metoda k–medoidów) z pakietu cluster. Liczbę klastrów (parametr k) będziemy wybierać spośród zbioru liczb naturalnych od \(2\) do \(30\).

2.1 Przykładowe klastry

Na poniższych wykresach zaprezentujemy przykładowe klasteryzacje:

3 Porównanie klasteryzacji

3.1 Wybór optymalnego parametru k

Spróbujemy teraz wybrać optymalną liczbę wykresów na podstawie błędu w klastrach:

Jak widać, metoda k–średnich zwróciła dość nieregularne wyniki (pojawiają się skoki wartości błedu), podczas gdy metoda k–medoidów w tym przypadku daje jednostajny spadek wartości funkcji celu w zależności od wartości parametru k.

Dla pierwszego algorytmów wybór najlepszego k nie będzie jednoznaczny – propozycjami (na podstawie wykresu, korzystając z tzw. metody łokcia) mogłyby być wartości \(8, 10\) lub \(20\). Dla drugiego algorytmu można zaproponować wartości \(18\) lub \(20\). Jako że \(20\) w obu przypadkach pojawia się w proponowanych, a ponadto wiemy, że jest to faktyczna liczba klastrów, ja zdecydowałbym się ją wybrać jako ostateczną wartość w obu przypadkach.

3.2 Porównanie klastrów dla k = 20

Spójrzmy teraz, jak wyglądają klastry dla wybranej liczby k

ggplot(data = cbind(dataset[, 1:2], cluster = kmeans_clusters[[19]]$cluster), 
       aes(x = x, y = y, group = cluster)) +
  geom_point(alpha = 0.7) +
  stat_voronoi(data = as.data.frame(kmeans_clusters[[19]]$centers), 
               aes(x = x, y = y),
               color = "red", size = 3, alpha = 0.9,
               geom = "path", outline = data.frame(x = c(-2, -2, 2, 2),
                                                   y = c(-2.5, 2, 2, -2.5),
                                                   group = c(1,1,1,1))) +
  stat_voronoi(data = as.data.frame(pam_clusters[[19]]$medoids), 
               aes(x = x, y = y),
               color = "blue", size = 3, alpha = 0.9,
               geom = "path", outline = data.frame(x = c(-2, -2, 2, 2),
                                                   y = c(-2.5, 2, 2, -2.5),
                                                   group = c(1,1,1,1)))

Na wykresie, niebieskie wielokąty reprezentują granicę klastrów k–medoidów, natomiast czerwone – k–średnich. Jak widzimy, klastry pam są bardziej zwarte niż klastry kmeans i reprezentują niemal idealny podział na grupki danych oryginalnych.

3.3 Porównanie centrów

ggplot(data = (dataset[, 1:2]), aes(x = x, y = y)) +
  geom_point(alpha = 0.7) +
  geom_point(data = as.data.frame(kmeans_clusters[[19]]$centers), 
               aes(x = x, y = y),
             color = "red", size = 5) +
  geom_point(data = as.data.frame(pam_clusters[[19]]$medoids), 
               aes(x = x, y = y),
             color = "blue", size = 5)

Na wykresie na niebiesko zaznaczone są k–medoidy, na czerwono k–średnie.

Główną różnicą pomiędzy centrami klastrów wynika z faktu różnicy między działaniem algorytmu – algorytm k–średnich wybiera pewną średnią między grupą punktów – i średnia ta sama niekoniecznie musi być punktem ze zbioru danych, podczas gdy w przypadku algorytmu k–medoidów środek klastra musi należeć do zbioru danych. Stąd w przypadku pierwszego algorytmu mogą powstawać takie sytuacje jak na powyższych wykresach – jeden z klastrów zawiera w sobie dwa dosyć wyraźnie odseparowane klastry.

4 Benchmark

Na koniec porównamy tempo zbieżności obu algorytmów. Policzymy czas zbieżności dla k \(= 10, \dots, 30\).

benchmark %>% 
  mutate( k = as.numeric(stri_sub(test, 1, 2)), 
          algorithm = stri_sub(test, 4)) %>% 
  select(k, algorithm, elapsed) %>%
  ggplot(aes(x = k, y = elapsed, color = algorithm)) +
    geom_line() +
    ggtitle("estimated convergency time (in seconds)")

Jak widzimy, algorytm k–medoidów z powodu swojej kwadratowej złożoności obliczeniowej jest wielokrotnie wolniejszy od błyskawicznego algorytmu k–średnich.

5 Podsumowanie

Algorytm k–medoidów będzie się sprawdzał lepiej niż algorytm k–średnich, gdy klastry są nie tak wyraźnie odseparowane, lecz każdy z nich ma rozkład w przybliżeniu normalny względem każdej ze zmiennych – w takim przypadku, nawet jeśli klastry na siebie nachodzą, względnie łatwo będzie wydzielić ich medianę, podczas gdy ze średnią może być trudniej. Algorytm ten będzie raczej nieskuteczny przy małej liczbie danych – wtedy również mediana będzie dla niego niewidoczna, jako że żadna z obserwacji może nie być blisko “prawdziwej” mediany rozkładu. Należy też pamiętać o jego znacznie dłuższym czasie obliczania.